The present invention relates to an FFT (Fast Fourier Transform) address generator, and more particularly to an FFT address generator which has simpler structure and higher speed than conventional models.
The FFT is probably one of the most important algorithms in digital signal processing (DSP) applications. There are two approaches for computing the transform: software implemented on a programmable DSP, and dedicated FFT processor development. Real-time DSP favors the use of the latter, which offers parallel processing capability.
An FFT processor hardware system mainly consists of two parts: the butterfly processor for arithmetic operation, and an address generator for the generation of read/write addresses. The address generator provides addresses of the operation data as well as the so-called "twiddle factors" W.sub.N.sup.k for each butterfly calculation. As is known, the FFT butterfly computation operates on data in sets of r points, where r is called the radix. A P-point FFT uses P/r butterfly units per stage for log.sub.r P stages. The computational result of one butterfly stage is the input data of next butterfly stage.
To meet the requirements of different signal flow graphs and different point numbers, the logic design of an FFT address generator is complicated, and arithmetic-logic-unit-like structures are often used. Addresses are generated through the execution of instructions. The propagation delay time of conventional FFT address generators is relatively high.